package Leetcode.Dichotomy;

import java.util.Arrays;

/**
 * @Author: kirito
 * @Date: 2024/4/4 14:30
 * @Description:
 *完成旅途的最少时间
 * 给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。
 *
 * 每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。
 *
 * 给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。
 *
 *
 *
 * 示例 1：
 *
 * 输入：time = [1,2,3], totalTrips = 5
 * 输出：3
 * 解释：
 * - 时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。
 *   已完成的总旅途数为 1 + 0 + 0 = 1 。
 * - 时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。
 *   已完成的总旅途数为 2 + 1 + 0 = 3 。
 * - 时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。
 *   已完成的总旅途数为 3 + 1 + 1 = 5 。
 * 所以总共完成至少 5 趟旅途的最少时间为 3 。
 * 示例 2：
 *
 * 输入：time = [2], totalTrips = 1
 * 输出：2
 * 解释：
 * 只有一辆公交车，它将在时刻 t = 2 完成第一趟旅途。
 * 所以完成 1 趟旅途的最少时间为 2 。
 *
 *
 * 提示：
 *
 * 1 <= time.length <= 105
 * 1 <= time[i], totalTrips <= 107
 */

public class minimumTime {
    public static void main(String[] args) {
        int[] nums = {66};
        int total = 8295;
        System.out.println(minimumTime2(nums, total));
    }
    public static long minimumTime1(int[] time, int totalTrips) {
        int count = 1;
        while (true) {
            int res = 0;
            for (int i = 0; i < time.length; i++) {
                res += count / time[i];
            }
            if (res >= totalTrips) {
                break;
            }
            count++;
        }
        return count;
    }

    public static long minimumTime2(int[] time, int totalTrips) {
        Arrays.sort(time);
        long left = time[0], right = (long) totalTrips * time[0];
        while (left <= right) {

            long mid = left + (right - left >> 1);
            int temp = toAns(time, mid, totalTrips);
            if (temp < totalTrips) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return left;
    }

    public static long minimumTime3(int[] times, int totalTrips) {
        Arrays.sort(times);//1.数组是无序的，反正题目没说有序，就默认无序
        long left = times[0], right = (long) totalTrips * times[0];
        while (left < right) {
            long mid = left + (right - left >> 1);
            if (toAns(times, mid, totalTrips) < totalTrips) {
                left = mid + 1;
                //2.↑这里注意，这个时间得到的旅途数目小于是不可能满足的所求的旅途数目的。所以直接+1排除mid
            } else {
                right = mid; //3.反之，能满足旅途数目 就不能排除。
            }
        }
        return right;//一波操作下来，直接返回能满足的right。left一直是无法满足的。(why?看第2条)
    }

    static int toAns(int[] times, long mid, int totalTrips) {
        int sum = 0;
        for (int time : times) {
            if (mid < time || sum >= totalTrips) {
                break;
            }
            sum += (mid / time);
        }
        return sum;
    }
}
